package cn.bellychang.skiplist.csdn;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author: bellychang
 * @date: 2020/2/6
 */
public class SkipListMap<K extends Comparable, V> {

    public static final double PROMOTION_FACTOR = 0.5d;
    private Node<K, V> head;
    private Node<K, V> tail;

    private int size;

    private int height;

    private int maxHeight;

    private Random random;

    public SkipListMap(int maxHeight) {
        head = new Node<>(null, null);
        tail = new Node<>(null, null);
        head.right = tail;
        tail.left = head;
        this.height = 1;
        this.maxHeight = maxHeight;
        random = new Random(System.currentTimeMillis());
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * need to consider duplicate Node
     *
     * @param key
     * @param value
     * @return
     */
    public SkipListMap<K, V> add(K key, V value) {
        Node lessNode = find(key);
        // judge if new or update
        if (lessNode.key != null && lessNode.key.equals(key)) {
            lessNode.value = value;
            return this;
        }
        Node<K, V> newNode = new Node<>(key, value);
        newNode.left = lessNode;
        newNode.right = lessNode.right;
        lessNode.right.left = newNode;
        lessNode.right = newNode;

        size++;

        int currentLayer = 1;
        // judge if need promotion layer
        while (random.nextDouble() < PROMOTION_FACTOR && height < maxHeight) {
            if (currentLayer >= height) {
                addEmptyUpperLayer();
            }
            // find the upper left node
            while (lessNode != null && lessNode.up == null) {
                // reach head or other left up node not null
                lessNode = lessNode.left;
            }
            // move to upper layer
            lessNode = lessNode.up;

            // upperNode do not need value
            Node upperNewNode = new Node<>(newNode.key, null);

            upperNewNode.left = lessNode;
            upperNewNode.right = lessNode.right;
            upperNewNode.down = newNode;
            newNode.up = upperNewNode;
            lessNode.right.left = upperNewNode;
            lessNode.right = upperNewNode;

            // ready for next promotion layer
            newNode = upperNewNode;
            currentLayer++;
        }
        return this;
    }

    public boolean contains(K key) {
        Node<K, V> temp = find(key);
        return temp.key.compareTo(key) == 0;
    }

    @Override
    public String toString() {
        List<String> list = new ArrayList<>(height);
        StringBuilder builder = new StringBuilder();
        Node headTemp = head;
        for (int i = 1; i <= height; i++) {
            Node temp = headTemp;
            while (temp != null) {
                builder.append(temp.toString())
                        .append("->");
                temp = temp.right;
            }
            list.add(builder.toString().substring(0, (builder.length() - 2)));
            builder.delete(0, builder.length());
            if (headTemp.down != null) {
                headTemp = headTemp.down;
            } else {
                break;
            }
        }
        return list.stream().collect(Collectors.joining("\\next line\\"));
    }

    public V get(K key) {
        Node<K, V> temp = this.find(key);
        if (temp.key == key) {
            return temp.value;
        }
        throw new NoSuchElementException();
    }

    /**
     * do not set temp = null, memory leak?
     *
     * @param key
     * @return
     */
    public V remove(K key) {
        Node<K, V> temp = this.find(key);
        V tempValue = temp.value;
        if (temp.key.compareTo(key)==0) {
            while (temp != null) {
                temp.left.right = temp.right;
                temp.right.left = temp.left;
                temp = temp.up;
            }
            size--;
            return tempValue;
        }
        throw new NoSuchElementException();
    }

    public void display() {
        List<String> list = new ArrayList<>(height);
        StringBuilder builder = new StringBuilder();
        Node headTemp = head;
        for (int i = 1; i <= height; i++) {
            Node temp = headTemp;
            while (temp != null) {
                builder.append(temp.toString())
                        .append("->");
                temp = temp.right;
            }
            list.add(builder.toString().substring(0, (builder.length() - 2)));
            builder.delete(0, builder.length());
            if (headTemp.down != null) {
                headTemp = headTemp.down;
            } else {
                break;
            }
        }
        list.stream().forEach(System.out::println);
    }

    /**
     * move head and tail to upper layer
     */
    private void addEmptyUpperLayer() {
        Node dummyHead = new Node<>(null, null);
        Node dummyTail = new Node<>(null, null);
        dummyHead.right = dummyTail;
        dummyTail.left = dummyHead;
        head.up = dummyHead;
        dummyHead.down = head;
        tail.up = dummyTail;
        dummyTail.down = tail;

        head = dummyHead;
        tail = dummyTail;
        height++;
    }

    /**
     * find node node.value <= element < node.right.value
     *
     * @param key
     * @return
     */
    private Node<K, V> find(K key) {
        if (isEmpty()) {
            return head;
        }
/*        if (head.right.key.compareTo(key) > 0) {
            return head;
        }*/
        Node temp = head.right;
        for (; ; ) {
            // not permit the tail
            while ((temp.right != null && temp.key.compareTo(key) <= 0)) {
                temp = temp.right;
            }
            // if temp = tail, choose tail.left
            temp = temp.left;
            if (temp.down != null) {
                temp = temp.down;
                // if temp is head
                temp = temp.right;
            } else {
                break;
            }
        }
        return temp;
    }

    private static class Node<E extends Comparable, V> {
        private E key;
        private V value;
        public Node<E, V> left, right, up, down;

        public Node(E key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            return builder.append(Optional.ofNullable(key).orElse((E) "null").toString())
                    .append("|")
                    .append(Optional.ofNullable(value).orElse((V) "null").toString())
                    .toString();
        }
    }

}
